SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>CURE algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">CURE algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r886047488">

/* start https://en.wikipedia.org/ */

.mw-parser-output .nobold{font-weight:normal}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar sidebar-collapse nomobile nowraplinks"><tbody><tr><td class="sidebar-pretitle">Part of a series on</td></tr><tr><th class="sidebar-title-with-pretitle"><a href="Machine_learning" title="Machine learning">Machine learning</a><br>and <a href="Data_mining" title="Data mining">data mining</a></th></tr><tr><td class="sidebar-content">

<ul><li><a href="Supervised_learning" title="Supervised learning">Supervised learning</a></li>

<li><a href="Unsupervised_learning" title="Unsupervised learning">Unsupervised learning</a></li>

<li><a href="Semi-supervised_learning" class="mw-redirect" title="Semi-supervised learning">Semi-supervised learning</a></li>

<li><a href="Self-supervised_learning" title="Self-supervised learning">Self-supervised learning</a></li>

<li><a href="Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></li>

<li><a href="Meta-learning_(computer_science)" title="Meta-learning (computer science)">Meta-learning</a></li>

<li><a href="Online_machine_learning" title="Online machine learning">Online learning</a></li>

<li><a href="Batch_learning" class="mw-redirect" title="Batch learning">Batch learning</a></li>

<li><a href="Curriculum_learning" title="Curriculum learning">Curriculum learning</a></li>

<li><a href="Rule-based_machine_learning" title="Rule-based machine learning">Rule-based learning</a></li>

<li><a href="Neuro-symbolic_AI" title="Neuro-symbolic AI">Neuro-symbolic AI</a></li>

<li><a href="Neuromorphic_engineering" class="mw-redirect" title="Neuromorphic engineering">Neuromorphic engineering</a></li>

<li><a href="Quantum_machine_learning" title="Quantum machine learning">Quantum machine learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<ul><li><a href="Statistical_classification" title="Statistical classification">Classification</a></li>

<li><a href="Generative_model" title="Generative model">Generative modeling</a></li>

<li><a href="Regression_analysis" title="Regression analysis">Regression</a></li>

<li><a href="Cluster_analysis" title="Cluster analysis">Clustering</a></li>

<li><a href="Dimensionality_reduction" title="Dimensionality reduction">Dimensionality reduction</a></li>

<li><a href="Density_estimation" title="Density estimation">Density estimation</a></li>

<li><a href="Anomaly_detection" title="Anomaly detection">Anomaly detection</a></li>

<li><a href="Data_cleaning" class="mw-redirect" title="Data cleaning">Data cleaning</a></li>

<li><a href="Automated_machine_learning" title="Automated machine learning">AutoML</a></li>

<li><a href="Association_rule_learning" title="Association rule learning">Association rules</a></li>

<li><a href="Semantic_analysis_(machine_learning)" title="Semantic analysis (machine learning)">Semantic analysis</a></li>

<li><a href="Structured_prediction" title="Structured prediction">Structured prediction</a></li>

<li><a href="Feature_engineering" title="Feature engineering">Feature engineering</a></li>

<li><a href="Feature_learning" title="Feature learning">Feature learning</a></li>

<li><a href="Learning_to_rank" title="Learning to rank">Learning to rank</a></li>

<li><a href="Grammar_induction" title="Grammar induction">Grammar induction</a></li>

<li><a href="Ontology_learning" title="Ontology learning">Ontology learning</a></li>

<li><a href="Multimodal_learning" title="Multimodal learning">Multimodal learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><div style="display: inline-block; line-height: 1.2em; padding: .1em 0;"><a href="Supervised_learning" title="Supervised learning">Supervised learning</a><br><span class="nobold"><span style="font-size: 85%;">(<b><a href="Statistical_classification" title="Statistical classification">classification</a></b> • <b><a href="Regression_analysis" title="Regression analysis">regression</a></b>)</span></span> </div></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Apprenticeship_learning" title="Apprenticeship learning">Apprenticeship learning</a></li>

<li><a href="Decision_tree_learning" title="Decision tree learning">Decision trees</a></li>

<li><a href="Ensemble_learning" title="Ensemble learning">Ensembles</a>

<ul><li><a href="Bootstrap_aggregating" title="Bootstrap aggregating">Bagging</a></li>

<li><a href="Boosting_(machine_learning)" title="Boosting (machine learning)">Boosting</a></li>

<li><a href="Random_forest" title="Random forest">Random forest</a></li></ul></li>

<li><a href="Linear_regression" title="Linear regression">Linear regression</a></li>

<li><a href="Naive_Bayes_classifier" title="Naive Bayes classifier">Naive Bayes</a></li>

<li><a href="Artificial_neural_network" class="mw-redirect" title="Artificial neural network">Artificial neural networks</a></li>

<li><a href="Logistic_regression" title="Logistic regression">Logistic regression</a></li>

<li><a href="Perceptron" title="Perceptron">Perceptron</a></li>

<li><a href="Relevance_vector_machine" title="Relevance vector machine">Relevance vector machine (RVM)</a></li>

<li><a href="Support_vector_machine" title="Support vector machine">Support vector machine (SVM)</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Cluster_analysis" title="Cluster analysis">Clustering</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="BIRCH" title="BIRCH">BIRCH</a></li>

<li><a href="Hierarchical_clustering" title="Hierarchical clustering">Hierarchical</a></li>

<li><a href="K-means_clustering" title="K-means clustering"><i>k</i>-means</a></li>

<li><a href="Fuzzy_clustering" title="Fuzzy clustering">Fuzzy</a></li>

<li><a href="Expectation%E2%80%93maximization_algorithm" title="Expectation–maximization algorithm">Expectation–maximization (EM)</a></li>

<li><br><a href="DBSCAN" title="DBSCAN">DBSCAN</a></li>

<li><a href="OPTICS_algorithm" title="OPTICS algorithm">OPTICS</a></li>

<li><a href="Mean_shift" title="Mean shift">Mean shift</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Dimensionality_reduction" title="Dimensionality reduction">Dimensionality reduction</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Factor_analysis" title="Factor analysis">Factor analysis</a></li>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Structured_prediction" title="Structured prediction">Structured prediction</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Graphical_model" title="Graphical model">Graphical models</a>

<ul><li><a href="Bayesian_network" title="Bayesian network">Bayes net</a></li>

<li><a href="Conditional_random_field" title="Conditional random field">Conditional random field</a></li>

<li><a href="Hidden_Markov_model" title="Hidden Markov model">Hidden Markov</a></li></ul></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Anomaly_detection" title="Anomaly detection">Anomaly detection</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Random_sample_consensus" title="Random sample consensus">RANSAC</a></li>

<li><a href="Local_outlier_factor" title="Local outlier factor">Local outlier factor</a></li>

<li><a href="Isolation_forest" title="Isolation forest">Isolation forest</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Neural_network_(machine_learning)" title="Neural network (machine learning)">Neural networks</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Autoencoder" title="Autoencoder">Autoencoder</a></li>

<li><a href="Deep_learning" title="Deep learning">Deep learning</a></li>

<li><a href="Feedforward_neural_network" title="Feedforward neural network">Feedforward neural network</a></li>

<li><a href="Recurrent_neural_network" title="Recurrent neural network">Recurrent neural network</a>

<li><a href="Reservoir_computing" title="Reservoir computing">reservoir computing</a></li></ul></li>

<li><a href="Boltzmann_machine" title="Boltzmann machine">Boltzmann machine</a>

<ul><li><a href="Restricted_Boltzmann_machine" title="Restricted Boltzmann machine">Restricted</a></li></ul></li>

<li><a href="Diffusion_model" title="Diffusion model">Diffusion model</a></li>

<li><a href="Convolutional_neural_network" title="Convolutional neural network">Convolutional neural network</a>

<li><a href="LeNet" title="LeNet">LeNet</a></li>

<li><a href="AlexNet" title="AlexNet">AlexNet</a></li>

<li><a href="DeepDream" title="DeepDream">DeepDream</a></li></ul></li>

<li><a href="Neural_field" title="Neural field">Neural field</a>

<ul><li><a href="Neural_radiance_field" title="Neural radiance field">Neural radiance field</a></li>

<li><a href="Physics-informed_neural_networks" title="Physics-informed neural networks">Physics-informed neural networks</a></li></ul></li>

<li><a href="Transformer_(deep_learning_architecture)" title="Transformer (deep learning architecture)">Transformer</a>

<ul><li><a href="Vision_transformer" title="Vision transformer">Vision</a></li></ul></li>

<li><a href="Mamba_(deep_learning_architecture)" title="Mamba (deep learning architecture)">Mamba</a></li>

<li><a href="Spiking_neural_network" title="Spiking neural network">Spiking neural network</a></li>

<li><a href="Memtransistor" title="Memtransistor">Memtransistor</a></li>

<li><a href="Electrochemical_RAM" title="Electrochemical RAM">Electrochemical RAM</a> (ECRAM)</li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Q-learning" title="Q-learning">Q-learning</a></li>

<li><a href="Policy_gradient_method" title="Policy gradient method">Policy gradient</a></li>

<li><a href="State%E2%80%93action%E2%80%93reward%E2%80%93state%E2%80%93action" title="State–action–reward–state–action">SARSA</a></li>

<li><a href="Temporal_difference_learning" title="Temporal difference learning">Temporal difference (TD)</a></li>

<li><a href="Multi-agent_reinforcement_learning" title="Multi-agent reinforcement learning">Multi-agent</a>

</tr><tr><td class="sidebar-content">

<ul><li><a href="Active_learning_(machine_learning)" title="Active learning (machine learning)">Active learning</a></li>

<li><a href="Crowdsourcing" title="Crowdsourcing">Crowdsourcing</a></li>

<li><a href="Human-in-the-loop" title="Human-in-the-loop">Human-in-the-loop</a></li>

<li><a href="Mechanistic_interpretability" title="Mechanistic interpretability">Mechanistic interpretability</a></li>

</tr><tr><td class="sidebar-content">

<ul><li><a href="Coefficient_of_determination" title="Coefficient of determination">Coefficient of determination</a></li>

<li><a href="Confusion_matrix" title="Confusion matrix">Confusion matrix</a></li>

<li><a href="Learning_curve_(machine_learning)" title="Learning curve (machine learning)">Learning curve</a></li>

<li><a href="Receiver_operating_characteristic" title="Receiver operating characteristic">ROC curve</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Mathematical foundations</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Kernel_machines" class="mw-redirect" title="Kernel machines">Kernel machines</a></li>

<li><a href="Bias%E2%80%93variance_tradeoff" title="Bias–variance tradeoff">Bias–variance tradeoff</a></li>

<li><a href="Computational_learning_theory" title="Computational learning theory">Computational learning theory</a></li>

<li><a href="Empirical_risk_minimization" title="Empirical risk minimization">Empirical risk minimization</a></li>

<li><a href="Occam_learning" title="Occam learning">Occam learning</a></li>

<li><a href="Probably_approximately_correct_learning" title="Probably approximately correct learning">PAC learning</a></li>

<li><a href="Statistical_learning_theory" title="Statistical learning theory">Statistical learning</a></li>

<li><a href="Vapnik%E2%80%93Chervonenkis_theory" title="Vapnik–Chervonenkis theory">VC theory</a></li>

<li><a href="Topological_deep_learning" title="Topological deep learning">Topological deep learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Journals and conferences</div><div class="sidebar-list-content mw-collapsible-content hlist">

<li><a href="Conference_on_Neural_Information_Processing_Systems" title="Conference on Neural Information Processing Systems">NeurIPS</a></li>

<li><a href="International_Joint_Conference_on_Artificial_Intelligence" title="International Joint Conference on Artificial Intelligence">IJCAI</a></li>

</tr><tr><td class="sidebar-content">

<ul><li><a href="Glossary_of_artificial_intelligence" title="Glossary of artificial intelligence">Glossary of artificial intelligence</a></li>

<li><a href="List_of_datasets_for_machine-learning_research" title="List of datasets for machine-learning research">List of datasets for machine-learning research</a>

<ul><li><a href="List_of_datasets_in_computer_vision_and_image_processing" title="List of datasets in computer vision and image processing">List of datasets in computer vision and image processing</a></li></ul></li>

<li><a href="Outline_of_machine_learning" title="Outline of machine learning">Outline of machine learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

<p><b>CURE</b> (Clustering Using REpresentatives) is an efficient <a href="Data_clustering" class="mw-redirect" title="Data clustering">data clustering</a> algorithm for large <a href="Database" title="Database">databases</a>. Compared with <a href="K-means_clustering" title="K-means clustering">K-means clustering</a> it is more <a href="Robust_statistics" title="Robust statistics">robust</a> to <a href="Outlier" title="Outlier">outliers</a> and able to identify clusters having non-spherical shapes and size variances.

</p>

<div class="mw-heading mw-heading2"><h2 id="Drawbacks_of_traditional_algorithms">Drawbacks of traditional algorithms</h2></div>

<p>The popular <a href="K-means_clustering" title="K-means clustering">K-means clustering</a> algorithm minimizes the <a href="Sum_of_squared_error" class="mw-redirect" title="Sum of squared error">sum of squared errors</a> criterion:

</p>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E=\sum _{i=1}^{k}\sum _{p\in C_{i}}(p-m_{i})^{2},}</annotation>

</semantics>

</math></span><img src="./eeb7a2c4e6c85822d195d8b7565fb3e247efce5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:22.7ex; height:7.676ex;" alt="{\displaystyle E=\sum _{i=1}^{k}\sum _{p\in C_{i}}(p-m_{i})^{2},}" loading="lazy"></span></dd></dl>

<p>Given large differences in sizes or geometries of different clusters, the square error method could split the large clusters to minimize the square error, which is not always correct. Also, with hierarchic clustering algorithms these problems exist as none of the distance measures between clusters (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{min},d_{mean}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{min},d_{mean}}</annotation>

</semantics>

</math></span><img src="./6d1e4ebfd4494929acb987cbab7de5e18adccce6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.977ex; height:2.509ex;" alt="{\displaystyle d_{min},d_{mean}}" loading="lazy"></span>) tend to work with different cluster shapes. Also the <a href="Analysis_of_algorithms" title="Analysis of algorithms">running time</a> is high when n is large.

</p><p>The problem with the <a href="BIRCH_(data_clustering)" class="mw-redirect" title="BIRCH (data clustering)">BIRCH algorithm</a> is that once the clusters are generated after step 3, it uses centroids of the clusters and assigns each <a href="Data_point" class="mw-redirect" title="Data point">data point</a> to the cluster with the closest centroid. Using only the centroid to redistribute the data has problems when clusters lack uniform sizes and shapes.

</p>

<div class="mw-heading mw-heading2"><h2 id="CURE_clustering_algorithm">CURE clustering algorithm</h2></div>

<p>To avoid the problems with non-uniform sized or shaped clusters, CURE employs a <a href="Hierarchical_clustering" title="Hierarchical clustering">hierarchical clustering</a> algorithm that adopts a <a href="https://en.wiktionary.org/wiki/middle_ground" class="extiw external" title="wikt:middle ground">middle ground</a> between the centroid based and all point extremes. In CURE, a constant number c of well scattered points of a cluster are chosen and they are shrunk towards the centroid of the cluster by a fraction α. The scattered points after shrinking are used as representatives of the cluster. The clusters with the closest pair of representatives are the clusters that are merged at each step of CURE's hierarchical clustering algorithm. This enables CURE to correctly identify the clusters and makes it less sensitive to outliers.

</p><p>Running time is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2}\log n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2}\log n)}</annotation>

</semantics>

</math></span><img src="./fd59427b9a6250e085bf2c29b06ef211c8e791e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.172ex; height:3.176ex;" alt="{\displaystyle O(n^{2}\log n)}" loading="lazy"></span>, making it rather expensive, and <a href="Computational_complexity_theory" title="Computational complexity theory">space complexity</a> is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math></span><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"></span>.

</p><p>The algorithm cannot be directly applied to large databases because of the high runtime complexity. Enhancements address this requirement.

</p>

<ul><li>Random sampling: <a href="Sampling_(statistics)" title="Sampling (statistics)">random sampling</a> supports large data sets. Generally the <a href="Random_sample" class="mw-redirect" title="Random sample">random sample</a> fits in <a href="Primary_storage" class="mw-redirect" title="Primary storage">main memory</a>. The random sampling involves a <a href="Trade-off" title="Trade-off">trade off</a> between accuracy and efficiency.</li>

<li>Partitioning: The basic idea is to partition the <a href="Sample_space" title="Sample space">sample space</a> into <i>p</i> partitions. Each partition contains <i>n/p</i> elements. The first pass partially clusters each partition until the final number of clusters reduces to <i>n/pq</i> for some constant q ≥ 1. A second clustering pass on <i>n/q</i> partially clusters partitions. For the second pass only the representative points are stored since the merge procedure only requires representative points of previous clusters before computing the representative points for the merged cluster. Partitioning the input reduces the execution times.</li>

<li>Labeling data on disk: Given only representative points for <i>k</i> clusters, the remaining data points are also assigned to the clusters. For this a fraction of randomly selected representative points for each of the <i>k</i> clusters is chosen and data point is assigned to the cluster containing the representative point closest to it.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<p><b>CURE (no. of points,<i>k</i>)</b>

</p><p>Input: A set of points S

</p><p>Output: <i>k</i> clusters

</p>

<ul><li>For every cluster u (each input point), in u.mean and u.rep store the mean of the points in the cluster and a set of <i>c</i> representative points of the cluster (initially <i>c</i> = 1 since each cluster has one data point). Also u.closest stores the cluster closest to u.</li>

<li>All the input points are inserted into a <a href="Kd-tree" class="mw-redirect" title="Kd-tree">k-d tree</a> T</li>

<li>Treat each input point as separate cluster, compute u.closest for each u and then insert each cluster into the heap Q. (clusters are arranged in increasing order of distances between u and u.closest).</li>

<li>While size (Q) > <i>k</i></li>

<li>Remove the top element of Q (say u) and merge it with its closest cluster u.closest (say v) and compute the new representative points for the merged cluster w.</li>

<li>Remove u and v from T and Q.</li>

<li>For all the clusters x in Q, update x.closest and relocate x</li>

<li>insert w into Q</li>

<li>repeat</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Availability">Availability</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://github.com/annoviko/pyclustering">pyclustering</a> open source library includes a Python and C++ implementation of CURE algorithm.</li></ul>

<ul><li><a href="K-means_clustering" title="K-means clustering">k-means clustering</a></li>

<li><a href="BFR_algorithm" title="BFR algorithm">BFR algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGuha,_SudiptoRastogi,_RajeevShim,_Kyuseok1998" class="citation journal cs1">Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (1998). <a rel="nofollow" class="external text" href="http://www.cs.sfu.ca/CC/459/han/papers/guha98.pdf">"CURE: An Efficient Clustering Algorithm for Large Databases"</a> <span class="cs1-format">(PDF)</span>. <i>Information Systems</i>. <b>26</b> (1): <span class="nowrap">35–</span>58. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0306-4379%2801%2900008-4">10.1016/S0306-4379(01)00008-4</a>.</cite></li>

<li><cite id="CITEREFKoganNicholas,_Charles_K.Teboulle,_M.2006" class="citation book cs1">Kogan, Jacob; Nicholas, Charles K.; Teboulle, M. (2006). <i>Grouping multidimensional data: recent advances in clustering</i>. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-28348-5</bdi>.</cite></li>

<li><cite id="CITEREFTheodoridisKoutroumbas,_Konstantinos2006" class="citation book cs1">Theodoridis, Sergios; Koutroumbas, Konstantinos (2006). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=gAGRCmp8Sp8C&pg=PA572"><i>Pattern recognition</i></a>. Academic Press. pp. <span class="nowrap">572–</span>574. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-12-369531-4</bdi>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-29" href="https://en.wikipedia.org/wiki/?title=CURE_algorithm&oldid=1282972435">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>